/* vim: set sw=8 ts=8 sts=8 expandtab: */
#include "Cmaid.h"
#include "cmaid_private.h"

/**
 * @defgroup Cmaid_Linked_List The Linked List Implementation
 * @ingroup Implementations
 * @brief The linked list implementation
 *
 * The linked list is a double linked list implementation, providing a
 * @ref Cmaid_List "list class". Insert, append and prepend are O(1) operations.
 */

typedef struct Cmaid_Linked_List Cmaid_Linked_List;
typedef struct Cmaid_Linked_List_Node Cmaid_Linked_List_Node;
typedef struct Cmaid_Linked_List_Node_Single Cmaid_Linked_List_Node_Single;

#define CMAID_LINKED_LIST(l) ((Cmaid_Linked_List *)(l))
#define CMAID_LINKED_LIST_NODE(n) ((Cmaid_Linked_List_Node *)(n))
#define CMAID_LINKED_LIST_NODE_SINGLE(n) ((Cmaid_Linked_List_Node_Single *)(n))

#define COMPARE_KEYS(cmp, n1, n2) cmp(CMAID_LINKED_LIST_NODE_SINGLE(n1)->key, \
                                        CMAID_LINKED_LIST_NODE_SINGLE(n2)->key)

struct Cmaid_Linked_List_Node
{
        Cmaid_Linked_List_Node *next;
        Cmaid_Linked_List_Node *previous;
};

struct Cmaid_Linked_List
{
        Cmaid_Container container;
        Cmaid_Linked_List_Node sentinel;
        Cmaid_Iter *iter_list;
        const Cmaid_Value *value;
};

struct Cmaid_Linked_List_Node_Single
{
        Cmaid_Linked_List_Node node;
        void *key;
};

/*
 * Declaration of the internal used functions
 */
/* container functions */
static void  cmaid_linked_list_clear(Cmaid_Container *c);
static void  cmaid_linked_list_iter_attach(Cmaid_Container *c, Cmaid_Iter *it);
static void  cmaid_linked_list_iter_detach(Cmaid_Container *c, Cmaid_Iter *it);
static void  cmaid_linked_list_destroy(Cmaid_Container *c);
static int   cmaid_linked_list_dump(Cmaid_Container *c, FILE *file);
/* list functions */
static void *cmaid_linked_list_append(Cmaid_List *t, const void *data);
static void *cmaid_linked_list_prepend(Cmaid_List *t, const void *data);
static void  cmaid_linked_list_first_remove(Cmaid_List *t);
static void  cmaid_linked_list_last_remove(Cmaid_List *t);
static void *cmaid_linked_list_first(Cmaid_List *t);
static void *cmaid_linked_list_last(Cmaid_List *t);
static void *cmaid_linked_list_insert_before(Cmaid_List *t, const Cmaid_Iter *it, const void *data);
static void *cmaid_linked_list_insert_after(Cmaid_List *t, const Cmaid_Iter *it, const void *data);
static void  cmaid_linked_list_sort_with(Cmaid_List *t,
                                                Cmaid_Value_Compare_Cb cmp);
static void  cmaid_linked_list_reverse(Cmaid_List *t);
/* iterator functions */
static void  cmaid_linked_list_iter_start(Cmaid_Iter *it);
static void *cmaid_linked_list_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it);
static void *cmaid_linked_list_iter_index_goto(Cmaid_Iter *it, int index);
static void *cmaid_linked_list_iter_goto(Cmaid_Iter *it, const void *data);
static void *cmaid_linked_list_iter_current(Cmaid_Iter *it);
static void *cmaid_linked_list_iter_next(Cmaid_Iter *it);
static void *cmaid_linked_list_iter_previous(Cmaid_Iter *it);
static void  cmaid_linked_list_iter_remove(Cmaid_Iter *it);
/* internal used functions */
static Cmaid_Linked_List_Node *cmaid_linked_list_node_mergesort(
                                        Cmaid_Linked_List_Node *first, int n,
                                        Cmaid_Value_Compare_Cb compare);
static Cmaid_Linked_List_Node *cmaid_linked_list_node_merge(
                                        Cmaid_Linked_List_Node *first,
                                        Cmaid_Linked_List_Node *second, 
                                        Cmaid_Value_Compare_Cb compare);

/*
 * The Interfaces
 */
const Cmaid_List_Interface cmaid_linked_list_list_if =
{
        {
                CMAID_MAGIC_LIST,
                cmaid_linked_list_clear,
                cmaid_linked_list_iter_attach,
                cmaid_linked_list_iter_detach,
                cmaid_linked_list_destroy,
                cmaid_linked_list_dump,
                NULL
        },
        cmaid_linked_list_append,
        cmaid_linked_list_prepend,
        cmaid_linked_list_first_remove,
        cmaid_linked_list_last_remove,
        cmaid_linked_list_first,
        cmaid_linked_list_last,
        cmaid_linked_list_insert_before,
        cmaid_linked_list_insert_after,
        cmaid_linked_list_sort_with,
        cmaid_linked_list_reverse
};

const Cmaid_Iter_Interface cmaid_linked_list_iter_if =
{
        cmaid_linked_list_iter_start,
        cmaid_linked_list_iter_iter_goto,
        cmaid_linked_list_iter_index_goto,
        cmaid_linked_list_iter_goto,
        cmaid_linked_list_iter_current,
        cmaid_linked_list_iter_next,
        cmaid_linked_list_iter_previous,
        cmaid_linked_list_iter_remove
};

/*
 * Public Functions
 */
/**
 * @param v The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used in the list
 * @return Returns a newly allocated @ref Cmaid_List "list", if an allocation 
 *        error occurs, @c NULL is returned
 * @brief Creates a new list using the hash implementation
 *
 * This functions is creating a @ref Cmaid_List "listt" with the linked list
 * as implementation.
 */
Cmaid_List *
cmaid_linked_list_new(const Cmaid_Value *v)
{
        Cmaid_Linked_List *l;

        l = CALLOC(1, sizeof(Cmaid_Linked_List));
        if (!l)
                return NULL;
        l->sentinel.next = l->sentinel.previous = &l->sentinel;
        CMAID_CONTAINER_INTERFACE_SET(l, &cmaid_linked_list_list_if);
        if (v)
                l->value = v;
        else
                l->value = &cmaid_value_pointer;

        return (Cmaid_List *) l;
}

/*
 * Helper functions
 */
CMAID_INLINE Cmaid_Linked_List_Node *
cmaid_linked_list_node_single_new(Cmaid_Linked_List *l, const void *data)
{
        void *key;
        Cmaid_Linked_List_Node_Single *node;

        node = cmaid_single_node_new(sizeof(Cmaid_Linked_List_Node_Single),
                                        l->value, data, 0, &key);
        node->key = key;
        key = NULL; /* only for testing clang */
        return (Cmaid_Linked_List_Node *)node;
}

static void
cmaid_linked_list_node_single_destroy(Cmaid_Linked_List *l, Cmaid_Linked_List_Node *node)
{
        cmaid_single_node_free(node, l->value,
                                CMAID_LINKED_LIST_NODE_SINGLE(node)->key);
}

static void
cmaid_linked_list_node_insert_between(Cmaid_Linked_List_Node *node, Cmaid_Linked_List_Node *first,
                                Cmaid_Linked_List_Node *second)
{
        second->previous = node;
        node->next = second;
        first->next = node;
        node->previous = first;
}

static Cmaid_Linked_List_Node *
cmaid_linked_list_node_remove(Cmaid_Linked_List_Node *node)
{
        node->next->previous = node->previous;
        node->previous->next = node->next;

        return node;
}

static void
cmaid_linked_list_iter_update_insert(Cmaid_Linked_List *l, int index)
{
        Cmaid_Iter *it;

        for (it = l->iter_list; it; it = it->next)
        {
                if (it->index >= index)
                        it->index++;
        }
}

static void
cmaid_linked_list_iter_update_remove(Cmaid_Linked_List *l, const Cmaid_Linked_List_Node *node, int id)
{
        Cmaid_Iter *it;

        for (it = l->iter_list; it; it = it->next)
        {
                if (it->index == id)
                {
                        it->current = node->previous;
                        it->index--;
                        if (it->current == &(l->sentinel))
                                it->index = -1;
                }
                else if (it->index > id)
                        it->index--;
        }
}

/*
 * The container functions implementation
 */
static void
cmaid_linked_list_clear(Cmaid_Container *c)
{
        Cmaid_Linked_List *l = CMAID_LINKED_LIST(c);
        Cmaid_Iter *it;

        /* remove everything from the list */
        while (l->sentinel.next != &(l->sentinel))
        {
                Cmaid_Linked_List_Node *node = cmaid_linked_list_node_remove(l->sentinel.next);
                cmaid_linked_list_node_single_destroy(l, node);
        }

        /* and set the iter to the end */
        for (it = l->iter_list; it; it = it->next)
        {
                it->current = &(l->sentinel);
                it->index = -1;
        }
        c->count = 0;
}

static void
cmaid_linked_list_iter_attach(Cmaid_Container *c, Cmaid_Iter *it)
{
        /* XXX we probably need to check if the iter isn't already in the 
         * list */
        it->interface = &cmaid_linked_list_iter_if;
        it->container = c;
        it->current = &(CMAID_LINKED_LIST(c)->sentinel);
        it->index = -1;

        /* insert into the iter list */
        it->next = CMAID_LINKED_LIST(c)->iter_list;
        CMAID_LINKED_LIST(c)->iter_list = it;
}


static void
cmaid_linked_list_iter_detach(Cmaid_Container *c, Cmaid_Iter *it)
{
        Cmaid_Iter **iter_list = &CMAID_LINKED_LIST(c)->iter_list;
        
        cmaid_iterlist_remove(iter_list, it);
}

static int
cmaid_linked_list_dump(Cmaid_Container *c, FILE *file)
{
        Cmaid_Linked_List *list = CMAID_LINKED_LIST(c);
        Cmaid_Linked_List_Node *node;
        Cmaid_Value_Stringify_Cb cb;
        char buffer[1024];

        cb = list->value->stringify ? list->value->stringify : cmaid_value_pointer_stringify;

        fprintf(file, "digraph list%p {\n", c);
        fprintf(file, "\tn%p [label=\"HEAD\"];\n", &list->sentinel);
        fprintf(file, "\tn%p -> n%p\n", &list->sentinel, list->sentinel.next);
        fprintf(file, "\tn%p -> n%p\n\n", &list->sentinel,
                        list->sentinel.previous);
        for (node = list->sentinel.next; node != &list->sentinel; node = node->next)
        {
                cb(CMAID_LINKED_LIST_NODE_SINGLE(node)->key, buffer,
                                sizeof(buffer));
                fprintf(file, "\tn%p [label=\"%s\"];\n", node, buffer);
                fprintf(file, "\tn%p -> n%p\n", node, node->next);
                fprintf(file, "\tn%p -> n%p\n\n", node, node->previous);
        }
        fprintf(file, "}\n");

        return TRUE;
}

static void
cmaid_linked_list_destroy(Cmaid_Container *c)
{
        cmaid_linked_list_clear(c);
        FREE(c);
}

/*
 * The list functions implementation
 */
static void *
cmaid_linked_list_prepend(Cmaid_List *t, const void *data)
{
        Cmaid_Linked_List *l = CMAID_LINKED_LIST(t);
        Cmaid_Linked_List_Node *node;

        node = cmaid_linked_list_node_single_new(l, data);
        if (!node)
                return NULL;

        cmaid_linked_list_node_insert_between(node, &(l->sentinel), l->sentinel.next);
        t->count++;
        cmaid_linked_list_iter_update_insert(l, 0);
        return CMAID_LINKED_LIST_NODE_SINGLE(node)->key;
}

static void *
cmaid_linked_list_append(Cmaid_List *t, const void *data)
{
        Cmaid_Linked_List *l = CMAID_LINKED_LIST(t);
        Cmaid_Linked_List_Node *node;

        node = cmaid_linked_list_node_single_new(l, data);
        if (!node)
                return NULL;

        cmaid_linked_list_node_insert_between(node, l->sentinel.previous,
                                                &(l->sentinel));
        t->count++;
        return CMAID_LINKED_LIST_NODE_SINGLE(node)->key;
}

static void
cmaid_linked_list_first_remove(Cmaid_List *t)
{
        Cmaid_Linked_List *l = CMAID_LINKED_LIST(t);
        Cmaid_Linked_List_Node *node;

        if (cmaid_container_empty_is(t))
                return;
        
        node = cmaid_linked_list_node_remove(l->sentinel.next);
        cmaid_linked_list_iter_update_remove(l, node, 0);
        cmaid_linked_list_node_single_destroy(l, node);
        t->count--;
}

static void
cmaid_linked_list_last_remove(Cmaid_List *t)
{
        Cmaid_Linked_List *l = CMAID_LINKED_LIST(t);
        Cmaid_Linked_List_Node *node;

        if (cmaid_container_empty_is(t))
                return;
        
        node = cmaid_linked_list_node_remove(l->sentinel.previous);
        cmaid_linked_list_iter_update_remove(l, node, t->count - 1);
        cmaid_linked_list_node_single_destroy(l, node);
        t->count--;
}

static void *
cmaid_linked_list_first(Cmaid_List *t)
{
        if (cmaid_container_empty_is(t))
                return NULL;

        return CMAID_LINKED_LIST_NODE_SINGLE(CMAID_LINKED_LIST(t)->sentinel.next)->key;
}

static void *
cmaid_linked_list_last(Cmaid_List *t)
{
        if (cmaid_container_empty_is(t))
                return NULL;

        return CMAID_LINKED_LIST_NODE_SINGLE(CMAID_LINKED_LIST(t)->sentinel.previous)->key;
}

static void *
cmaid_linked_list_insert_before(Cmaid_List *t, const Cmaid_Iter *it,
                                const void *data)
{
        Cmaid_Linked_List *l = CMAID_LINKED_LIST(t);
        Cmaid_Linked_List_Node *node;

        node = cmaid_linked_list_node_single_new(l, data);
        if (!node)
                return NULL;

        cmaid_linked_list_node_insert_between(node,
                                        CMAID_LINKED_LIST_NODE(it->current)->previous,
                                               CMAID_LINKED_LIST_NODE(it->current));
        t->count++;
        /* if the index is -1 it is equal to an append, so we don't need
         * to update the iterators */
        if (it->index > -1)
                cmaid_linked_list_iter_update_insert(l, it->index);

        return CMAID_LINKED_LIST_NODE_SINGLE(CMAID_LINKED_LIST(t)->sentinel.previous)->key;
}

static void *
cmaid_linked_list_insert_after(Cmaid_List *t, const Cmaid_Iter *it,
                                const void *data)
{
        Cmaid_Linked_List *l = CMAID_LINKED_LIST(t);
        Cmaid_Linked_List_Node *node;

        node = cmaid_linked_list_node_single_new(l, data);
        if (!node)
                return NULL;

        cmaid_linked_list_node_insert_between(node,
                                CMAID_LINKED_LIST_NODE(it->current),
                                       CMAID_LINKED_LIST_NODE(it->current)->next);
        t->count++;
        cmaid_linked_list_iter_update_insert(l, it->index + 1);        
        
        return CMAID_LINKED_LIST_NODE_SINGLE(CMAID_LINKED_LIST(t)->sentinel.previous)->key;
}

static void
cmaid_linked_list_sort_with(Cmaid_List *t, Cmaid_Value_Compare_Cb cmp)
{
        Cmaid_Linked_List *l = CMAID_LINKED_LIST(t);
        Cmaid_Linked_List_Node *first, *last;

        /* lists with less then two items are already sorted */
        if (t->count < 2)
                return;

        /* take the right compare function */
        if (!cmp)
                cmp = (l->value->cmp) ? l->value->cmp
                        : cmaid_value_pointer_compare;

        /* first we make our circular list to a list with begin and end */
        first = l->sentinel.next;
        first->previous = NULL;
        last = l->sentinel.previous;
        last->next = NULL;

        l->sentinel.next = cmaid_linked_list_node_mergesort(first, t->count, cmp);
        /* We still need the end of the list, let's start with the last end */
        while (last->next)
                last = last->next;
        l->sentinel.previous = last;

        /* make it a circular list again */
        l->sentinel.next->previous = &(l->sentinel);
        l->sentinel.previous->next = &(l->sentinel);

        /* XXX what should we do with the iterators? */
}

static Cmaid_Linked_List_Node *
cmaid_linked_list_node_mergesort(Cmaid_Linked_List_Node *first, int n,
                Cmaid_Value_Compare_Cb compare)
{
        Cmaid_Linked_List_Node *middle;
        Cmaid_Linked_List_Node *premid;
        int mid;
        int i;

        if (n < 2)
                return first;
        else if (n == 2)
        {
                if (COMPARE_KEYS(compare, first, first->next) > 0)
                {
                        /* we need to swap the data here. Since this is not 
                         * possible, we are going to swap the whole node */
                        Cmaid_Linked_List_Node *second = first->next;

                        first->next = NULL;
                        first->previous = second;
                        second->next = first;
                        second->previous = NULL;

                        return second;
                }
                return first;
        }

        mid = n/2;

        /* first find the premiddle node*/
        for (premid = first, i = 0; i < mid - 1; i++)
                premid = premid->next;

        /* split the list */
        middle = premid->next;
        premid->next = NULL;
        middle->previous = NULL;

        /* sort the the partial lists */
        first = cmaid_linked_list_node_mergesort(first, mid, compare);
        middle = cmaid_linked_list_node_mergesort(middle, n - mid, compare);

        return cmaid_linked_list_node_merge(first, middle, compare);
}

/* this function is used to merge the partial sorted lists */
static Cmaid_Linked_List_Node *
cmaid_linked_list_node_merge(Cmaid_Linked_List_Node *first,
                                Cmaid_Linked_List_Node *second, 
                                Cmaid_Value_Compare_Cb compare)
{
        Cmaid_Linked_List_Node *list;
        Cmaid_Linked_List_Node *l;

        /* select the first node outside the loop, because we need to keep
         * a pointer to it */
        if (COMPARE_KEYS(compare, first, second) > 0)
        {
                list = l = second;
                second = second->next;
        }
        else
        {
                list = l = first;
                first = first->next;
        }

        /* and now start the merging */
        while (first && second)
        {
                if (COMPARE_KEYS(compare, first, second) > 0)
                {
                        second->previous = l;
                        l = l->next = second;
                        second = second->next;
                }
                else
                {
                        first->previous = l;
                        l = l->next = first;
                        first = first->next;
                }
        }

        /* append the rest or set it to NULL */
        if (first) 
        {
                first->previous = l;
                l->next = first;
        }
        else if (second)
        {
                second->previous = l;
                l->next = second;
        }
        else
                l->next = NULL;

        return list;
}
static void
cmaid_linked_list_reverse(Cmaid_List *t)
{
        Cmaid_Linked_List *l = CMAID_LINKED_LIST(t);
        Cmaid_Linked_List_Node *current;
        
        current = &l->sentinel;
        do
        {
                Cmaid_Linked_List_Node *tmp;

                /* swap the next and the previous pointer */
                tmp = current->next;
                current->next = current->previous;
                current->previous = tmp;

                current = current->next;
        }
        while (current != &l->sentinel);
}

/*
 * The iterator functions implementation
 */
static void
cmaid_linked_list_iter_start(Cmaid_Iter *it)
{
        it->index = -1;
        it->current = &CMAID_LINKED_LIST(it->container)->sentinel;
}

static void *
cmaid_linked_list_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it)
{
        if (!to_it || it->container != to_it->container)
                return NULL;

        it->index = to_it->index;
        it->current = to_it->current;
        return cmaid_linked_list_iter_current(it);
}

static void *
cmaid_linked_list_iter_index_goto(Cmaid_Iter *it, int index)
{
        Cmaid_List *l = it->container;
        int i;

        if (l->count == 0 || index >= l->count || index < 0)
        {
                cmaid_linked_list_iter_start(it);
                return NULL;
        }

        if (it->index < 0)
        {
                if (index > l->count/2)
                        cmaid_linked_list_iter_previous(it);
                else
                        cmaid_linked_list_iter_next(it);
        }

        if (index < it->index)
                for (i = it->index; i != index; i--)
                        cmaid_linked_list_iter_previous(it);
        else
                for (i = it->index; i != index; i++)
                        cmaid_linked_list_iter_next(it);

        return CMAID_LINKED_LIST_NODE_SINGLE(it->current)->key;
}

static void *
cmaid_linked_list_iter_goto(Cmaid_Iter *it, const void *data)
{
        void * found;

        cmaid_linked_list_iter_start(it);
        while ((found = cmaid_linked_list_iter_next(it)) && found != data)
                ;

        return found;
}

static void *
cmaid_linked_list_iter_current(Cmaid_Iter *it)
{
        if (it->current == &(CMAID_LINKED_LIST(it->container)->sentinel))
                return NULL;

        return CMAID_LINKED_LIST_NODE_SINGLE(it->current)->key;
}

static void *
cmaid_linked_list_iter_next(Cmaid_Iter *it)
{
        it->current = CMAID_LINKED_LIST_NODE(it->current)->next;
        if (it->current != &(CMAID_LINKED_LIST(it->container)->sentinel))
        {
                it->index++;
                return CMAID_LINKED_LIST_NODE_SINGLE(it->current)->key;
        }

        it->index = -1;
        return NULL;
}

static void *
cmaid_linked_list_iter_previous(Cmaid_Iter *it)
{
        if (it->current == &(CMAID_LINKED_LIST(it->container)->sentinel))
                it->index = CMAID_CONTAINER(it->container)->count;

        it->current = CMAID_LINKED_LIST_NODE(it->current)->previous;
        if (it->current == &(CMAID_LINKED_LIST(it->container)->sentinel))
        {
                it->index = -1;
                return NULL;
        }
        it->index--;

        return CMAID_LINKED_LIST_NODE_SINGLE(it->current)->key;
}

static void
cmaid_linked_list_iter_remove(Cmaid_Iter *it)
{
        Cmaid_Linked_List *l = CMAID_LINKED_LIST(it->container);
        Cmaid_Linked_List_Node *node;

        if (it->current == &(CMAID_LINKED_LIST(it->container)->sentinel))
                return;
        
        node = cmaid_linked_list_node_remove(it->current);
        cmaid_linked_list_iter_update_remove(l, it->current, it->index);
        cmaid_linked_list_node_single_destroy(l, node);
        CMAID_CONTAINER(it->container)->count--;
}


